This is a test file which can be used to practice file transfers. It can be freely redistributed without restriction. If a SYSOP finds this file uploaded to their service, they should assume the uploader was merely practicing uploads and should delete the file.
---
The Turing Machine is a concept that was introduced in 1936 by the British mathematician Alan Turing as a method to express algorithms. What made the idea of the Turing Machine popular was the fact that with only paper and pencil, it is possible to simulate the operation of a computer (even though computers in the modern sense of the word did not yet exist.) In mathematical terms, a Deterministic Turing Machine is a sextuple (A, B, C, D, E, F) where:
A is a finite set of states;
B is an alphabet of tape symbols;
C is a start state: C in A;
D is a function: z = D(x,y): x in A, y in B, z in B;
E is a function: z = E(x,y): x in A, y in B, z in {left, right, stop};
F is a function: z = F(x,y): x in A, y in B, z in A;
In more informal terms, a Turing Machine can be thought of as a control unit, a read/write head, and a tape. The control unit is a finite state machine which contains actions associated with each state. When the Turing Machine is operating, the control unit uses the current state entry indexed by the current input symbol (the symbol under the read/write head) to locate the write symbol, tape movement direction and next state. The control unit writes a new tape symbol at the current head location, moves the tape either left or right and changes to a new state. The following shows the basic Turing Machine "hardware" along with a sample deterministic control unit.
Turing Machines come in two varieties: Deterministic and Non-Deterministic. The above example is of a Deterministic Turing Machine. The difference between that and a Non-Deterministic Turing Machine is that there can be more than one entry in the control unit table for a particular state and input symbol. When the control unit needs to execute from a state which has multiple entries, the selecton of which entry to execute is non-deterministic.
One thing to note about the Turing Machine is that it assumes infinite resources. The tape is of infinite length (is it extendable in either direction), and there is no limit on execution time.
The individual characteristics of a Turning Machine are determined by the control unit. When someone asks if two Turning Machines are the same, they are asking if the control units are the same. "Programming" in terms of a Turing Machine does not refer to changing the control unit, but instead refers to writing a program on the tape. It is the job of the control unit to "execute" the "program" stored on the tape.
To make this concept more concrete, we use the example of the contemporary micro-programmed micro-processor. In such a processor, the internal control unit is "micro-programmed", and it is this micro-programming which gives the micro-processor its personality. For example, the Intel 8088 and Motorola 68000 are both examples of micro-programmed micro-processors. By changing the micro-programming in the 68000, it is possible to make it execute the instruction set used by the Intel 8088. When you change the control unit on a Turing Machine or a micro-processor, you change the machine itself. When you change the program in a Turning Machine or micro-processor, you just change the contents of the tape or memory which is executed by the control unit, not the control unit.
The range of programs which can be executed by a Turing Machine is limited by the control unit. A very simple control unit may only be able to execute a small subset of all possible programs while there are more advanced control units which can execute all programs that can be executed on any Turing Machine. Turing Machines which have the ability to execute all possible programs that could be executed on any other Turing Machines are said to be "universal." A Universal Turing Machine is analagous to a general purpose micro-processor.
Currently, the smallest known control unit for a Universal Turing Machine was developed by Marvin Minsky in 1962. The control unit consisted of four symbols and seven states. With a control unit table of only 28 entries, this machine can execute any program that can be executed on any other special purpose or Universal Turing Machine. Minsky also conjectured that there existed a three symbol, six state Universal Turing Machine, but it has never been proven.
While no longer being the focus of a great deal of research, the Turing Machine holds the distinction of truly being one of the first "personal computers" before the term came into general use. The concept behind the Turing Machine is so simple that it can be explained to most anyone. Yet, at the same time, it serves as a model which is powerful enough to compute the same class of programs as can be solved with today's most powerful machines. While the Turing Machine itself may no longer be widely used as a model of computation, it does serve as a reminder of the underlying simplicity today's computers.
References:
Minsky, M.L., Size and Structure of Universal Turing Machines Using Tag Systems, Marcel Dekker (1962), 229-238.
Wood, Derick, Theory of Computation, John Wiley and Sons, (1987), 280-337.
